package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Date;



//希尔排序：（从大到小）在插入排序的前提下先使用增量将一组数据进行大概的编排，使得大的数基本排在前面，
//小的数基本排在后面，当增量等于1时就是传统的插入排序（避免应该排在很前面的数在排序前排在很后面，需要经过移动很多次才到前面）
public class ShellSort {

	public static void main(String[] args) {
		// int[] nums={3,5,1,8,4,7};
		int[] nums = new int[8000000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = (int) (Math.random() * 8000000);
		}
		Date d1 = new Date();
		SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");// 日期格式
		System.out.println("排序前的时间：" + s.format(d1));
		for (int gap = nums.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < nums.length; i++) {
				int index = i;
				int value = nums[index];
				while (index >= gap && value > nums[index - gap]) {
					nums[index] = nums[index - gap];
					index -= gap;
				}
				nums[index] = value;
			}
		}
		// System.out.println(Arrays.toString(nums));
		Date d2 = new Date();
		System.out.println("排序后的时间：" + s.format(d2));
	}
}
